I. Field of the Disclosure
The technology of the disclosure relates to filters for determining membership of an item in a collection of items, such as cache lines stored in a cache memory, for example.
II. Background
Cache memory is used to store a subset of items contained in a larger, primary memory. Cache memory offers faster access to data than a primary memory, but cache memory is more costly to implement than a primary memory. Consequently, a cache memory is usually smaller than the associated primary memory.
A primary memory may have multiple associated cache memories. Thus, data associated with the same primary memory location may be stored in more than one cache memory at a time. In this scenario, a cache coherency mechanism is used to ensure that different cache memories do not contain different data associated with the same primary memory location. One such mechanism involves each respective cache memory sending a notification, sometimes referred to as a “snoop probe,” to all other cache memories upon the occurrence of a particular event, such as a modification to data contained in the respective cache memory. A snoop probe commonly includes an identifier identifying a particular memory location of the data that has been modified. Each cache memory that receives the snoop probe then determines whether that memory location is contained within the respective cache. As the number of cache memories associated with a primary memory increases, the number of snoop probes increases.
Accessing cache memory to determine the presence of an identified memory location can be time-consuming and processor intensive, increasing power utilization of an associated cache controller. Consequently, cache memories have associated filter mechanisms to filter out snoop probes that identify a memory location that is not contained within the respective cache memory. One such filter mechanism that can be used for cache memory is a Bloom filter. Bloom filters are advantageous in that they provide a relatively fast mechanism for determining presence of a memory address in a collection without returning false negatives. A Bloom filter may include a number of mapping functions, each of which has an associated array of counters. When data is stored in the associated cache memory, the memory location of the data is also provided to the Bloom filter. Each mapping function processes the memory location to map the memory location to a respective counter, which is then incremented. When data is removed or invalidated in the associated cache memory, the memory location of the affected data is provided to the Bloom filter. Each mapping function processes the memory location to map the memory location to the appropriate counter that was incremented when a cache line was added to the cache memory. The respective counters are then decremented. The mapping functions may map multiple memory locations to the same counter.
Upon receipt of a snoop probe from another cache memory, each mapping function processes the identified memory location to determine a respective counter. If any of the counters to which the memory location is mapped are zero, the particular mapped memory location is not contained in the associated cache memory, and the Bloom filter need not forward the snoop probe to the cache memory. However, if each of the counters mapped to an identified memory location has a non-zero value, the identified memory location may be contained in the associated cache memory. Thus, the Bloom filter forwards the snoop probe to the cache memory for determination of whether or not the identified memory location is contained in the cache memory. Therefore, the Bloom filter provides a relatively fast mechanism for filtering out snoop probes associated with memory locations that cannot be contained in the cache memory, reducing power consumption of the cache memory. A Bloom filter may return a false positive result that erroneously indicates that a memory location is contained in a cache memory. However, a Bloom filter may not return a false negative that erroneously indicates that an identified memory location is not contained in a cache memory.
Because the mapping functions in a Bloom filter may map more than one memory location to the same counter, the counters must be of sufficient size to track all memory locations that can be mapped to a counter. Otherwise, the counters could be incremented past their maximum or saturation value and contain an invalid value where the counters can no longer be relied upon. As a result, the filter could generate false negatives and jeopardize cache coherency. Providing counters of a size sufficient to properly track all possible memory locations mapped to counters in a filter incurs cost and requires devoting area on a semiconductor die and/or integrated circuit. Reducing area dedicated to cache memory may be particularly desired for small and/or portable computer processing unit (CPU)-based devices.